from typing import Optional

from python.mypackage.TreeNode import TreeNode


"""
 方法： 使用栈实现二叉搜索树的中序遍历迭代器
 
 Args:
     root: Optional[TreeNode] - 二叉搜索树的根节点
 
 Returns:
     BSTIterator: 二叉搜索树迭代器实例
 
 Time: 
     - 构造方法: O(h) - h为树的高度，需要遍历到最左节点
     - next(): 均摊O(1) - 每个节点最多入栈出栈一次
     - hasNext(): O(1) - 直接检查栈是否为空
 
 Space: O(h) - h为树的高度，栈中最多存储h个节点
"""
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        while root:
            self.stack.append(root);
            root = root.left

    def next(self) -> int:
        cur = self.stack.pop()
        node = cur.right
        while node:
            self.stack.append(node)
            node = node.left
        return cur.val
        

    def hasNext(self) -> bool:
        return len(self.stack) > 0